package com.example.demo.algorithm.priority;

/**
 * @Author: xiatian
 * @CreateTime: 2022/1/31 11:10 上午
 * @Description: 索引最小优先队列(通过索引获取元素)
 */
public class IndexMinPriorityQueue<T extends Comparable<T>> {
    //存储堆中的元素
    private T[] items;
    //保存每个元素在items数组中的索引，pq数组需要堆有序
    private int[] pq;
    //保存qp的逆序，pq的值作为索引，pq的索引作为值
    private int[] qp;
    //记录堆中的元素个数
    private int N;

    public IndexMinPriorityQueue(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.pq = new int[capacity + 1];
        this.qp = new int[capacity + 1];
        N = 0;
        //默认情况下qp逆序中不存储任何索引，让qp中的元素都为-1
        for (int i = 0; i < qp.length; i++) {
            qp[i] = -1;
        }
    }

    //获取队列中的元素的个数
    public int size() {
        return N;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 判断堆中索引i处的元素是否小于索引j处的元素
     *
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j) {
        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }

    /**
     * 交换堆中索引i和j索引处的值
     *
     * @param i
     * @param j
     */
    private void exch(int i, int j) {
        //交换pq中的数据
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
        //更新qp中的数据
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    /**
     * 判断k对应的元素是否存在
     *
     * @param k
     * @return
     */
    public boolean contains(int k) {
        //默认情况下qp中的所有元素都是-1，如果某个位置插入了数据，则不为-1
        return qp[k] != -1;
    }

    /**
     * 最小元素关联的索引
     *
     * @return
     */
    public int minIndex() {
        //pq的索引1处，存放最小元素在items中的索引
        return pq[1];
    }

    /**
     * 往队列中插入一个元素,并关联索引i
     *
     * @param t
     */
    public void insert(int i, T t) {
        //如果索引i处已存在元素，则不让插入
        if (contains(i)) {
            return;
        }
        N++;
        //把数据存储到items对应的位置处
        items[i] = t;
        //把i存储到pq中
        pq[N] = i;
        //通过qp来记录pq中的i
        qp[i] = N;
        //通过堆的上浮完成堆的调整,让pq有序
        swim(N);
    }

    /**
     * 删除堆中最小的元素，并返回这个最小的元素的索引
     *
     * @return
     */
    public int delMin() {
        //找到items中最小的元素的索引
        int minIndex = pq[1];
        //交换pq中索引1出的值和N处的值
        exch(1, N);
        //删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        //删除pq中索引N处的值
        pq[N] = -1;
        //删除items中的最小元素
        items[minIndex] = null;
        //元素-1
        N--;
        //对pq[1]做下沉，让堆有序
        sink(1);
        return minIndex;
    }

    /**
     * 删除索引i关联的元素
     *
     * @param i
     */
    public void delete(int i) {
        //找出i在pq中的索引
        int k = qp[i];
        //把pq中索引k处的值和索引N处的值交换
        exch(k, N);
        //删除qp中索引pq[N]处的值
        qp[pq[N]] = -1;
        //删除pq中索引N处的值
        pq[N] = -1;
        //删除items中索引i处的值
        items[i] = null;
        //元素-1
        N--;
        //对pq[k]做下沉，让堆有序
        sink(k);
        //对pq[k]做上浮，让堆有序
        swim(k);
    }

    //把与索引i关联的元素修改为为t
    public void changeItem(int i, T t) {
        //修改items数组中索引i处的值为t items[i] = t; //找到i在pq中的位置
        int k = qp[i];
        //对pq[k]做下沉，让堆有序
        sink(k);
        //对pq[k]做上浮，让堆有序
        swim(k);
    }

    /**
     * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
     *
     * @param k
     */
    private void swim(int k) {
        //通过循环，不断比较当前节点和其父节点，如果父节点的值比当前节点的值大，则交换位置
        while (k > 1) {
            if (less(k, k / 2)) {
                exch(k, k / 2);
            }
            //变换k的位置继续比较
            k = k / 2;
        }
    }

    /**
     * 使用下沉的算法，使索引k的元素能在堆中处于一个正确的位置
     *
     * @param k
     */
    private void sink(int k) {
        while (2 * k <= N) {
            //找到k处的子节点的最小值
            int minChildIndex = 2 * k;
            if (2 * k + 1 <= N) {
                if (less(2 * k + 1, 2 * k)) {
                    minChildIndex = 2 * k + 1;
                }
            }
            //如果k的元素小于子节点的最大值，则结束循环
            if (less(k, minChildIndex)) {
                break;
            }
            //判断k处的元素和子节点的最小元素的大小，如果k的元素大于子节点的最大值，则交换位置
            exch(k, minChildIndex);
            //变换k的值
            k = minChildIndex;
        }
    }


}
